The OSPF protocol is a protocol of the Transmission Control Protocol/Internet Protocol (TCP/IP) family making it possible for the routing systems or “routers” of an Internet network to have sufficient knowledge of the network to route the received packets correctly to their destinations.
The particularity of the OSPF protocol is that it is a dynamic routing protocol, i.e. it is capable of taking account of changes in the topology of the network in dynamic manner. For this purpose, the protocol has steps in which messages are exchanged periodically, in order to update constantly the knowledge that each router possesses of the network or of a portion of the network.
A router has connections with other routers. These connections can be of various types, such as:
point to point networks;
multi-access networks, e.g. of the Ethernet™ type; and
stub networks making it possible to interconnect a set of host stations.
As a function of the type of connection and of the status of the router, it can be necessary to put the router into adjacency with another router.
Putting two routers into adjacency consists in ensuring that they share exactly the same data about the topology of the network.
In some cases, it is not necessary to put two routers into adjacency. For example, in a multi-access network, for optimization reasons, adjacency is implemented only between each router and a router that is elected to be the designated router.
In the OSPF protocol, the designated router R1 exchanges various types of messages with the neighboring routers, such as Database Description Packet (DDP) messages, “Hello” messages, data transmission (Link State (LS) Update) messages, data request (LS Request) messages, and acknowledgement of receipt (LS Acknowledgement) messages.
The object of the “Hello” messages is to inform the other routers periodically that the issuer of the message is still active.
The LS Update messages make it possible to receive data about the routers making up the network, while the LS Request messages make it possible to request data about the routers.
In compliance with the OSPF protocol, each router has a routing table that makes it possible to forward correctly the messages that it receives. Because of the dynamic aspect of the network, the routing tables must be constantly updated.
These updates are effected in particular by exchanging messages containing fragmentary information about the network and referred to as Link State Advertisement (LSA) messages. The routing tables are calculated by each router on the basis of this data.
The LS Update messages are in fact collections of LSA fragmentary data.
A third type of message is the Database Description Packet (DDP) message. These messages make it possible for two routers to exchange LSA summary lists, i.e. descriptions of the contents of their databases.
The various messages are described more fully in above-mentioned RFC 2328.
In the OSPF protocol, provision is also made to associate a state machine with each router that is a neighbor of a router.
FIG. 1 represents such a state machine. As is conventional, the circles represent the states which the interface can occupy. At any given time, the interface must be in one of these states. Each arrow in the diagram represents a transition from one state to another. The names of the states are given in the diagram, as they appear in RFC 2328.
The initial state of the state machine is represented by the circle referenced “Down”.
When the router receives a “Hello” message, the “Hello Received” event is generated and the state machine goes to an “Init” state. The “Start” event is generated when a “Hello” message must be generated firstly by the router, in a non-broadcast multiple access network. In which case, the state machine goes to the “Attempt” state. A “Hello” message being received in response then generates a “Hello Received” event, and the state machine goes to the “Init” state.
As a function in particular of the connection and of the status of the router, the arrival of a “2-way Received” event causes the state machine to go either to an “ExStart” state or to a “2-way” state.
The “2-way” state is reached when the type of connection does not need adjacency to be formed between the two routers. This applies, for example, if they are members of a multi-access network and if neither of the two routers is a designated router. This state is a stable state but it can be called into question by the arrival of a “1-way Received” event indicating that the connection between the two routers has encountered a problem, and that the state machine must return to the “Init” state.
The “ExStart” state is reached when it is necessary to put the two routers into adjacency. During this state, the router negotiates with its counterpart in order to determine a master and a slave, by sending DDP messages without data.
Once this negotiation has been performed, a “NegotiationDone” event occurs and the state machine goes to the “Exchange” state.
During this state, the two routers exchange DDP messages.
Once the two routers have exchanged the description of all of their data, the “ExchangeDone” event occurs.
There are then two possibilities:
either both routers have the same data about the network; they are thus in adjacency, and the state machine goes to the “Full” state;
or else there is divergence, and the router that has the least up to date data makes a request (LS Request) to the other router to transmit a data exchange message in order to update its data; for this purpose, the state machine goes to the “Loading” state.
Conventionally, when a router system is re-started, e.g. after a failure, the state machine thus has to re-start in the “Down” state. The other router is then warned of this change, and it can also be subjected to a change of state.
Clearly, a state machine following the path once again from the “Down” state to an end state such as “2-way” or “Full” takes a long time and can generate heavy traffic over the network (exchanging DDP messages, etc.).
In order to minimize the consequences of the router failing or of it being shut down temporarily for maintenance purposes, it is possible to provide for redundancy in the routers: a router on standby becomes active when the active router stops, e.g. after a failure or after an intentional shut down for maintenance.
Such a solution is, in particular, implemented by Cisco, in the Hot Standby Router Protocol (HSRP).
Another redundancy solution is described in IETF's RFC 2338, entitled “Virtual Router Redundancy Protocol”.
However, in that solution as well, when a first router in the active state fails and causes the standby second router to take over, the state machines managing the routers that are neighbors of the router in question must re-start in the “Down” state.
That results in the second router being unavailable for a time lapse before it can return to the state in which the first router was before it failed or stopped. Conventionally, that delay is at least 40 seconds and is generally about 1 minute.
The state machines re-starting also suffers from the drawback of causing changes in the states of the neighboring routers.